#include <stdio.h>
#include <stdlib.h>
//线性表之循环链表
//内容：判断是否有环，环的入口在哪
typedef int ElemType;
typedef struct node
{
    ElemType data;
    struct node *next;
}Node;
Node *Initlist()
{
    Node *s=(Node *)malloc(sizeof(Node));
    s->data=0;
    s->next=NULL;
    return s;
}
Node* addtail(Node *ps,ElemType n)
{
    Node*p=ps;
    while(p->next)
    {
        p=p->next;
    }
    Node * q=(Node*)malloc(sizeof(Node));
    q->data=n;
    p->next=q;
    q->next=NULL;
    return q;
}
//1️⃣判断是否有环（快慢指针）
//快指针和慢指针都指向头节点，快指针一次走两步，满指针一次走一步
//链表结束内，即快指针不指向NULL或快指针指针域不是NULL
//快指针和慢指针相遇就证明有环
int huan(Node *ps)
{
    Node *first=ps;
    Node *slow=ps;
    while(first!=NULL&&first->next!=NULL)
    {
        first=first->next->next;
        slow=slow->next;
        if(first==slow)
        {
            return 1;
        }
    }
    return 0;
}
//2️⃣环的入口
//让快指针和慢指针再走一圈到达第二次相遇，就可以知道这个环有多少个节点
//快慢指针都回到头节点，环节点数就是first比slow先多走的步数，二者再一起出发，每次都走一步
//相遇时，即在入口处，因为快指针多走的步数正好完整环绕环一圈
//或者另一种方法：当快慢指针相遇后，再让一个指针从头开始走，另一个指针继续走，二者每次走一步，相遇即入口
Node *kou(Node *ps)
{
    Node *first=ps;
    Node *slow=ps;
    while(first!=NULL&&first->next!=NULL)
    {
        first=first->next->next;
        slow=slow->next;
        if(first==slow)
        {
            break;
        }
    }
    slow=ps;
    while(first!=NULL&&first->next!=NULL)
    {
        first=first->next;
        slow=slow->next;
        if(first==slow)
        {
            printf("入口是%d\n",first->data);
            return slow;
        }
    }
}
//释放链表(头节点也被释放)
//从环的起始点开始，先释放环外，再释放环
void freelist(Node *ps,Node *h)
{
    if(ps==NULL)
    return;
    Node *p=ps;
    Node *q;
    while(p!=h)
    {
        q=p->next;
        free(p);
        p=q;
    }
    Node *a=h->next;
    Node *b;
    do
    {
        b=a->next;
        free(a);
        a=b;
    } while (a!=h);
    free(a);
}
int main()
{
    Node *list=Initlist();
    addtail(list,1);
    addtail(list,2);
    Node *three=addtail(list,3);
    addtail(list,4);
    addtail(list,5);
    addtail(list,6);
    addtail(list,7);
    Node *tail=addtail(list,8);
    tail->next=three;
    if(huan(list))
    {
        printf("有环\n");
    }
    else
    {
        printf("没环\n");
    }
    //环的入口
    Node *h=kou(list);
    freelist(list,h);
    return 0;
}